package leetcode4;

public class Day8 {


    public static void main(String[] args) {
        int[] a = {1,2};
        findPeakElement(a);
    }

    public static int findPeakElement(int[] nums) {
        //左边和右边是无穷很小，说明中间的区间[0,n-1]是肯定存在峰值的
        int n = nums.length - 1;
        int left = 0, right = n - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] < nums[mid+1]) { //mid mid+1区间是上升趋势/，说明峰值在右边肯定存在一个（因为右边区域无穷小）
                left = mid + 1;
            }else { //mid mid+1是下降趋势，说明答案在左边存在一个（最左边区域区域无穷小）
                right = mid;
            }
        }
        return left;
    }

    public int mySqrt(int x) {
        //寻找右端点,mid ^ 2
        //左边区间：num[x] <= mid^2 ;右边区间：num[x] > mid^2
        //为什么？要舍去小数部分，说明平分大于x，则不存在答案
        if(x == 0) return 0;
        long left = 1, right = x;
        while(left < right) {
            long mid = left + (right - left + 1)/2;
            if(mid * mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return (int)left;
    }




}
